package 动态规划.经典动态规划题目.戳气球;

public class 戳气球_312 {
    public int maxCoins(int[] nums) {
        int n = nums.length;

        //添加两侧虚拟的气球
        int[] points = new int[n + 2];
        points[0] = points[n + 1] = 1;//首尾两端添加的虚拟气球，硬币数量置为1

        for (int i = 1; i <= n; i++) {
            points[i] = nums[i - 1];
        }

        //base case 已经都被初始化为0
//dp[i][j]=x：戳破气球i和j之间（开区间，不包括i、j）的所有气球可获得的最大硬币数量为x
        int dp[][] = new int[n + 2][n + 2];

        for (int i = n; i >= 0; i--) {
            for (int j = i + 1; j < n + 2; j++) {
                //k：开区间(i,j)中最后被戳破的那个气球
                /*
                dp[i][k]+dp[k][j]+points[i]*points[j]*points[k]：
                先戳破(i,k)的气球，再戳破(k,j)的气球，最后戳破k
                */
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j],
                            dp[i][k] + dp[k][j] + points[i] * points[j] * points[k]);
                }
            }
        }
        return dp[0][n + 1];
    }
}
